public class BinarySearchTree {

 

    static class TreeNode {

        public int val;

        public TreeNode left;

        public TreeNode right;

 

        TreeNode(int val) {

            this.val = val;

        }

    }

 

    public TreeNode root;

 

    /**

     * 插入一个元素

     * @param key

     */

    public boolean insert(int key) {
        TreeNode treeNode = new TreeNode(key);
        //空树时,直接插入
        if (root == null){
            root = treeNode;
            return true;
        }
        TreeNode cur = root;
        TreeNode pre = null;
        //找到叶子节点
        while (cur != null){
            //遍历:比根节点大就right,比根节点小就left
            if (cur.val > key){
                pre = cur;
                cur = cur.left;
            }else if(cur.val < key){
                pre = cur;
                cur = cur.right;
            }else {
                //当key与cur.val相等时,直接return false,因为二叉搜索树中每个值只能存在一个
                return false;
            }
        }
        //在叶子节点上add
        if (pre.val < key){
            pre.right = treeNode;
        }else {
            pre.left = treeNode;
        }
        return true;

    }

    /**
     * 查找key是否存在
     * @param key
     * @return
     */

    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < key) {
                cur = cur.right;
            }else if(cur.val > key) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

    /**
     *  删除key的值
     */


    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key) {
                parent = cur;
                cur = cur.left;
            }else {
                //找到了 就要开始删除了
                removeNode(cur,parent);
                return true;
            }
        }
        return false;
    }
    public void removeNode(TreeNode cur,TreeNode parent){
        /**
         * 三种情况:
         * 1.cur.left == null
         * 2.cur.right == null
         * 3.cur.left != null && cur.right != null
         */

        /**
         * 一:cur.left == null
         * 1. cur 是 root，则 root = cur.right
         * 2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
         * 3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
         */
        if (cur.left == null){
            if (cur == root){
                root = cur.right;
            }else{
                if (cur == parent.left){
                    parent.left = cur.right;
                }else if (cur == parent.right){
                    parent.right = cur.right;
                }
            }
        }else if (cur.right == null){
            /**
             * 二:cur.right == null
             * 1. cur 是 root，则 root = cur.left
             * 2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
             * 3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
             */
            if (cur == root){
                root = cur.left;
            }else {
                if (cur == parent.left){
                    parent.left = cur.left;
                }else if(cur == parent.right){
                    parent.right = cur.left;
                }
            }
        }else{
            /**
             * 三:cur.left != null && cur.right != null
             * 替换法进行删除，即在它的   "右子树"   中寻找中序下的第一个结点(关键码最小)，用它的值填补到被
             * 删除节点中，再来处理该结点的删除问题
             */
            //在cur的右边找到最小值,如果能找到其左数一定为空
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            //一直找左树,寻找最小值
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            //分两种情况
            if(targetParent.left == target) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }

        }
    }
}